home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 14 / CU Amiga Magazine's Super CD-ROM 14 (1997)(EMAP Images)(GB)(Track 1 of 3)[!][issue 1997-09].iso / CUCD / Programming / Mesa-2.2 / src-glu / README1 < prev    next >
Encoding:
Text File  |  1995-04-28  |  8.8 KB  |  196 lines
  1.  
  2. Notes on the GLU polygon tesselation facility implemented by Bogdan Sikorski...
  3.  
  4.  
  5.  
  6. The tesselation module is provided under the same terms as the Mesa
  7. package.
  8.  
  9. This is the first release of polygon tesselation code for Mesa.
  10. It was written during my very little free time, so lets name it:
  11. "its not perfect". If someone hates pointers, don't look at the code.
  12. I preffer dynamic allocation versus static. But _all_ ideas, suggestions,
  13. bug reports and fixes are welcome (if You want, also flames). I am aware
  14. that many things could have been written using better techniques, but time
  15. that I could devote to this library was very limited. It is not well commented,
  16. excuse me. Also I am thinking of continuing working on this code to improve,
  17. fix and polish it. And make it as compliant as possible to the OpenGL, so
  18. software ports from OpenGL to Mesa will work correctly. If You know of any
  19. differences in behaviour, expected input/output between Mesa tesselation library
  20. and OpenGL, please send me a note. I explain later on why I am not
  21. confident with this code.
  22.  
  23. I tried to be fully compliant with the OpenGL routines. By "tried" I mean that
  24. up to my knowledge it behaves as OpenGL tesselation routines. Just recently
  25. I began to experiment with OpenGL (actually only Mesa), and also have
  26. no access to any machine providing official implementation of OpenGL,
  27. nor access to books (particulary Addison-Wesley publications). Thus my
  28. knowledge on how the original tesselation code works, what kind of data
  29. it expects etc. is based _only_ on the publicly available documentation
  30. provided by SGI. Namely:
  31.  
  32. * "The OpenGL Graphics System Utility Library" by K.P.Smith
  33.     (Silicon Graphics, 1992)
  34. * "The OpenGL Graphics Interface" by M.Segal and K.Akeley
  35.     (Silicon Graphics, 19??)
  36. * "OpenGL and X, Part 1: Introduction" by M.J.Kilgard
  37.     (Silicon Graphics, 1994)
  38. * "OpenGL and X, Part 2: Using OpenGL with Xlib" by M.J.Kilgard
  39.     (Silicon Graphics, 1994)
  40. * "OpenGL Graphics with the X Window System" by P.Karlton
  41.     (Silicon Graphics, 1993)
  42. * Online Docs - Appendix C of OpenGL Programming Guide, Polygon Tesselation
  43.      (partial text cut and sent by e-mail)
  44.  
  45.  
  46. The tesselation routines use slightly different prototypes than the ones
  47. specified in the mentioned above publications. The _only_ differences are
  48. the enumeration types which are not GLenum, but are GLUenum. So the
  49. implemented routines have following prototypes:
  50.  
  51. GLUtringulatorObj *gluNewTess(void);
  52.  
  53. void gluTessCallback(GLUtriangulatorObj *,GLUenum,void (*)());
  54.                                           ^^^^^^^
  55. void gluBeginPolygon(GLUtriangulatorObj *);
  56.  
  57. void gluTessVertex(GLUtriangulatorObj *,GLdouble [3],void *);
  58.  
  59. void gluNextContour(GLUtriangulatorObj *,GLUenum);
  60.                                          ^^^^^^^
  61. void gluEndPolygon(GLUtriangulatorObj *);
  62.  
  63. const GLubyte *gluErrorString(GLUenum);
  64.                               ^^^^^^^
  65.     prototypes for callback functions:
  66.  
  67. void <begin>(GLUenum);
  68.              ^^^^^^^
  69. void <edgeFlag>(GLboolean);
  70. void <vertex>(void *);
  71. void <end>(void);
  72. void <error>(GLUenum);
  73.              ^^^^^^^
  74.  
  75. The begin callback will be called only with GLU_TRIANGLES. No support
  76. for traingle fans or strips yet.     
  77.  
  78. In case of errors an internal error variable is set to the appropiate 
  79. error enum values (GLU_TESS_ERROR?). Initially it is set to GLU_NO_ERROR.
  80. The OpenGL library provides 8 error conditions, the tesselation code
  81. of Mesa provides 9. They are:
  82.  
  83. GLU_TESS_ERROR1: missing gluEndPolygon                  /* same as OpenGL */
  84. GLU_TESS_ERROR2: missing gluBeginPolygon                /* same as OpenGL */
  85. GLU_TESS_ERROR3: misoriented contour                    /* not used in Mesa
  86.                          in OpenGL is bad orientation or intersecting edges */
  87. GLU_TESS_ERROR4: vertex/edge intersection               /* same as OpenGL */
  88. GLU_TESS_ERROR5: misoriented or self-intersecting loops /* same as OpenGL */
  89. GLU_TESS_ERROR6: coincident vertices                    /* same as OpenGL */
  90. GLU_TESS_ERROR7: colinear vertices                      /* OpenGL's illegal data */
  91. GLU_TESS_ERROR8: intersecting edges                     /* same as OpenGL */
  92. GLU_TESS_ERROR9: not coplanar contours                  /* new for Mesa */
  93.  
  94. The Mesa tesselation code ignores all data and calls after detecting an error
  95. codition. This means that a _new_ tesselation object must be used for further
  96. triangulations. Maybe this is too restrictive, and will be lifted in
  97. future versions.
  98.  
  99. The tesselation code completely ignores the type parameter passed in
  100. gluNextContour. It also doesn't check if the passed parameter is a legal
  101. enum value - ignores silently (maybe at least this should be checked).
  102. The reason I chose this behaviour is based on what I read in the 
  103. beforementioned documents. I cite:
  104.  
  105. "....
  106. void gluNextContour(GLUtriangulatorObj *tessobj, GLenum type);
  107.  
  108. Marks the beginning of the next contour when multiple contours make up the
  109. boundary of the polygon to be tessellated. type can be GLU_EXTERIOR,
  110. GLU_INTERIOR, GLU_CCW, GLU_CW, or GLU_UNKNOWN. These serve only as 
  111. to the tessellation. If you get them right, the tessellation might
  112. go faster. If you get them wrong, they're ignored, and the tesselation still
  113. works.
  114. ....."
  115.  
  116. I hope You agree with me that my decision was correct. Mesa tesselation
  117. _always_ checks by itself the interrelations between contours. Just as if
  118. all contours were specified with the type GLU_UNKNOWN.
  119.  
  120. One of OpenGL's policy is not to check all error conditions - rely sometimes
  121. that the user "got things right". This is justified, since exhausting
  122. error checking is timeconsuming, and would significantly slow down
  123. a correct application. The Mesa tesselation code assumes only _one_ condition
  124. when triangulating - all vertices in a contour are planar. This is _not_
  125. checked for correctness. Trying to tesselate such objects will lead to
  126. unpredictable output.
  127.  
  128. And now we arrive to the moment where I would like to list the required
  129. (but checked for) conditions for triangulation, as well as summarize the
  130. library:
  131.  
  132. * all contours in a single tesselation cycle _must_ be coplanar - if not
  133.     an error is raised (and if provided a call to the error callback
  134.     is made)
  135. * the contours can be passed in _any_ order, exteriors and holes can be
  136.     intermixed within a tesselation cycle and the correct hierarchy
  137.     will be determined by the library; thus specifying first holes then
  138.     exteriors, then holes within holes form a valid input.
  139. * a hole within a hole is consider to be a yet another exterior contour
  140. * multiple exterior contours (polygons) can be tesselated in one cycle;
  141.     _but_ this significantly degrades performance since many tests will be
  142.     performed for every contour pair; if You want triangulation to be fast
  143.     tesselate a single polygon (with possible holes) one at a time.
  144. * orientation of exterior contours is arbitray, but if it has holes,
  145.     all interior holes of this particular exterior contour _must_ have an
  146.     opposite orientation.
  147. * the output triangles have the same orientation as the exterior contour
  148.     that forms them
  149. * each triangle is "enclosed" within the begin and end callbacks;
  150.     this is not efficent, but was made on purpose; so if triangulation
  151.     results in 2 triangles the following callbacks will be made in such
  152.     order:
  153.     <begin>(GLU_TRAINGLES)
  154.     <vertex>(...) /* 3 vertices of first triangle */
  155.     <vertex>(...)
  156.     <vertex>(...)
  157.     <end>()
  158.     <begin>(GLU_TRAINGLES)
  159.     <vertex>(...) /* 3 vertices of second triangle */
  160.     <vertex>(...)
  161.     <vertex>(...)
  162.     <end>()
  163.     Of course only when begin, vertex, and end callback were provided,
  164.     otherwise no output is done (actually tesselation does not take place).
  165. * You will notice that some output traingles are very "thin"; there
  166.     exist possible several ways to traingulate a polygon, but "smart" code
  167.     avoiding such cases would require time to write, and will impact on
  168.     execution speed.
  169. * like OpenGL, no new vertices are introduced during triangulation
  170. * if the edgeflag callback is provided it will be called whenever
  171.     the just-about-to be output vertex begins a different type of edge
  172.     than the previous vertices; always before the first output a call
  173.     is made with GL_TRUE, to allow synchronization.
  174. * all intermediate computations are done using GLdouble type, and comparisons
  175.     are biased with a precision value (EPSILON defined in tess.h)
  176. * the point_in_poly function is my adaptation of code from the
  177.     comp.graphics.alg newsgroup FAQ (originally written by Mr. Wm. Randolph
  178.     Franklin, modified by Scott Anguish).
  179. * the edge_edge_intersect test is also an adopted code from comp.graphics.alg
  180.     newsgroup FAQ
  181. * the general idea for traingulation used in this library is described in
  182.     the book "Computational Geometry in C" by Joseph O'Rourke.
  183.  
  184.  
  185. Excuse my English, its not my mother tongue. I should be available for some
  186. time uner the following e-mail address. But For how long I am not certain.
  187. Once I am settled in my new place, I'll post on the Mesa mailing list
  188. my new address.
  189.  
  190. (PS: today is my last day of work here, I'm changing my job).
  191.  
  192. Bogdan. ( bogdan@dia.unisa.it )
  193.  
  194. Apr 28, 1995.
  195.  
  196.